package jobs.job5.lru;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;


/*
 LUR缓存器，最近最少使用原则，参考 https://blog.csdn.net/qq_46517733/article/details/123092629
 核心思想，
 1. 使用哈希表+链表的结构，哈希表用于缓存元素，链表顺序储存元素，
 2. 且越靠后的元素活跃度越高，越不可能在短期内被删除，越在前的数据，活跃度越低，当缓存器装满元素时，删除活跃度最低的元素
 3. 当某个元素被访问时，此元素放到链表尾部，因此具有最高活跃度。

 实现细节
 1. 通常服务于某个组件，比如nosql数据库。这里伪造数据库，有求必应，任何key都能响应一个value。
 2. 这里实现 get、put、delete 方法。
 3. get、put方法，都将key对应元素的活跃度提升到最高
 */
public abstract class LRURegister<K, V> {

    //    缓存数据的结构
    static class Node<K, V> {
        K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    //    储存缓存数据的map
    Map<K, Node<K, V>> map;
    //    用于储存活跃度的链表
    LinkedList<Node<K, V>> list;
    //    LRU缓存器的容量，超过这个容量的最少使用元素将会被删除
    int capacity;

    public LRURegister(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }

    //    通过缓存器，根据key获取Value
    public V get(K key) {
        if (map.containsKey(key)) {    //缓存中存在
            Node<K, V> node = map.get(key);     //则缓存中直接获取
            list.remove(node);  //先删除
            list.addLast(node); //在添加到尾部，使得该节点的活跃度为最高
            return node.value;
        } else {
            Node<K, V> node = new Node<>(key, getFromDatabase(key)); // 否则从数据库中获取
            list.addLast(node);                           // 添加到缓存，根据最近原则，该节点刚刚被访问过，具有最高活跃度。添加到尾部
            map.put(key, node);                           // 添加到map中
            checkCapacity();        // 检测缓存容量达到最大
            return node.value;
        }
    }

//    缓存放一份，数据库放一份，并改变数据的活跃度
    public void put(K key, V value) {
        Node<K, V> node;
        if (map.containsKey(key)) {    //缓存中存在
            node = map.get(key);       //则缓存中直接获取
            node.value = value;        // 更新缓存中的值
            list.remove(node);         //先删除
        } else {
            node = new Node<>(key, value); // 缓存中不存在，否则创建新节点
            map.put(key, node);            // 添加到map缓存中
            checkCapacity();        // 检测缓存容量达到最大
        }
        list.addLast(node); //在添加到尾部，使得该节点的活跃度为最高
        putIntoDatabase(key, value);  //将数据放入数据库中
    }

    public V delete(K key) {
        if (map.containsKey(key)) {    //缓存中存在
            Node<K, V> node = map.remove(key);     //从缓存中直接删除
            list.remove(node);  //删除
        }
        return deleteFromDatabase(key); //从数据库中删除
    }

    // 检测缓存容量达到最大
    private void checkCapacity() {
        if (list.size() > capacity) {       // 如果缓存满了
//                则此时根据最少使用原则，删除活跃度最低的元素，既删除头部元素
            Node<K, V> older = list.removeFirst();  //链表中删除
            map.remove(older.key); // 根据链表中删除的元素的key，在map中删除
        }//或许考虑每次删除多个活跃度低的元素（优化）
    }

    // LRU 缓存器服务于某个数据库，具体访问数据库细节不是LRU关心的。
    abstract V getFromDatabase(K key);
    abstract void putIntoDatabase(K key, V value);
    abstract V deleteFromDatabase(K key);

    public static void main(String[] args) {

//        使用一个伪造的数据库
        FakeDatabase fakeDatabase = new FakeDatabase();
//        创建lru缓存器，服务于伪造的数据库
        LRURegister<String, String> lruRegister = new LRURegister<String, String>(6) {
            @Override
            String getFromDatabase(String key) {
                return fakeDatabase.get(key);
            }

            @Override
            void putIntoDatabase(String key, String value) {
            }

            @Override
            String deleteFromDatabase(String key) {
                return null;
            }
        };

//        下面的例子可以验证LRU 缓存是有效的
        for (int i = 0; i < 10; i++)
            System.out.println(i + "," + lruRegister.get(String.valueOf(i)));

        System.out.println("-----------");

        for (int i = 0; i < 10; i++)
            System.out.println(i + "," + lruRegister.get(String.valueOf(i)));

        System.out.println("-----------");

        for (int i = 9; i >= 0; i--)
            System.out.println(i + "," + lruRegister.get(String.valueOf(i)));
    }
}


